//------------------------------------------------------------------
// Purpose:     This program demonstrates bucket_sort.
// Author:      John Gauch
//------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cstdlib> 
#include "list3/list3.h"
using namespace std;

//---------------------------------------------------------------------
// Prompt user for program parameters. 
//---------------------------------------------------------------------
void get_parameters(int &num_values, float &min, float &max, int &num_buckets)
{
   // Prompt user for program parameters
   string str;
   cout << "Enter number of data values: ";
   cin >> str;
   num_values = stoi(str);

   cout << "Enter minimum data value: ";
   cin >> str;
   min = stof(str);

   cout << "Enter maximum data value: ";
   cin >> str;
   max = stof(str);

   cout << "Enter number of buckets: ";
   cin >> str;
   num_buckets = stoi(str);
}

//------------------------------------------------------------------
// Initialize data array with random values between min and max.
//------------------------------------------------------------------
void random_data(float data[], int num_values, float min, float max)
{
   // Put random numbers into data array
   for (int index = 0; index < num_values; index++)
      data[index] = min + rand() * (max - min) / RAND_MAX;
}

//------------------------------------------------------------------
// Check to see if data is correctly sorted
//------------------------------------------------------------------
bool check_sorted(float data[], int num_values)
{
   // Put random numbers into data array
   bool sorted = true;
   for (int index = 1; index < num_values; index++)
      if (data[index-1] > data[index])
         sorted = false;
   return sorted;
}

//------------------------------------------------------------------
// Write data array to output file.
//------------------------------------------------------------------
void write_data(string name, float data[], int count)
{
   // Open output file
   ofstream dout;
   dout.open(name.c_str());
   if (dout.fail())
      cout << "Error: could not open output file\n";

   // Write the data
   dout << count;
   for (int i = 0; i < count; i++)
   {
      if (i % 20 == 0)
	 dout << endl;
      dout << data[i] << " ";
   }

   // Close the file
   dout << endl;
   dout.close();
}

//----------------------------------------------------------------
// Bucket_sort algorithm.
//----------------------------------------------------------------
void bucket_sort(float data[], int num_values, float min, float max,
		 int num_buckets)
{
   // Create buckets
   List bucket[num_buckets];

   // Put unsorted data into buckets
   for (int index = 0; index < num_values; index++)
   {
      int num = int(num_buckets * (data[index] - min) / (max - min));
      if (num < 0) num = 0;
      else if (num >= num_buckets) num = num_buckets-1;
      bucket[num].SortedInsert(data[index]);
   }

   // Extract sorted data from buckets
   int index = 0;
   for (int num = 0; num < num_buckets; num++)
      while (!bucket[num].IsEmpty())
	 bucket[num].DeleteHead(data[index++]);
}

//---------------------------------------------------------------------
// main program to test sorting functions
//---------------------------------------------------------------------
int main()
{
   // Get program parameters
   int num_values, num_buckets;
   float min, max;
   get_parameters(num_values, min, max, num_buckets);

   // Generate random input data
   float * data = new float[num_values];
   random_data(data, num_values, min, max);

   // Sort data using bucket sort
   write_data("data.unsorted", data, num_values);
   bucket_sort(data, num_values, min, max, num_buckets);
   write_data("data.sorted", data, num_values);

   // Check data is sorted
   if (!check_sorted(data, num_values))
      cout << "Error sorting data" << endl;
   delete []data;
}